\section{Related Work}\label{sec:relatedwork}

The problem of finding size-bounded densest subgraphs has been studied extensively in the classical setting. Finding a maximum density subgraph in an undirected graph can be solved in polynomial time~\cite{G84,L}. However, the problem becomes NP-hard when a size restriction is enforced. In particular, finding a maximum density subgraph of size exactly $k$ is NP-hard~\cite{AHI,FKP} and no approximation scheme exists under a reasonable complexity assumption~\cite{K}. Recently Bhaskara et al.~\cite{BCVGZ12} showed integrality gaps for SDP relaxations of this problem.
% Recently, Andersen and Chellapilla~\cite{AC} considered approximation algorithms to this and other similar problems.
Khuller and Saha~\cite{KS} considered the problem of finding densest subgraphs with size restrictions and showed that these are NP-hard. Khuller and Saha~\cite{KS} and also Andersen and Chellapilla~\cite{AC} gave constant factor approximation algorithms. Some of our algorithms are based on of those presented in~\cite{KS}.

%-Algorithms branch from those in Khuller and Saha~\cite{KS} and other past work such as~\cite{AC}.
% Done so commenting - Atish


%-\amitabh{Discuss model:}
 %This is a  widely used  standard model
% to study distributed algorithms and captures the realistic notion that
%there is a bound on the amount of messages that can be sent through
%an edge in one time step  and hence captures the bandwidth
%constraints inherent
% in  real-world computer  networks \cite{peleg, PK09}.
 % (We note that if unbounded-size messages were allowed through every
%edge in each time step, then the problems addressed here can be
%trivially solved in $O(D)$ time by collecting all  the topological information %at
%one node, solving the problem locally, and then broadcasting the
%results back to all the nodes \cite{peleg}.)
%\atish{Should we mention here explicitly that we do not consider message complexity - the total number of messages exchanged. And admit that our algorithm is expensive in this aspect?}
% Many fundamental network problems such as minimum spanning tree, shortest paths, etc. have been addressed in this model (e.g., see \cite{lynch, peleg, PK09}). In particular, there has been much research into designing very fast distributed   approximation
%algorithms (that are even faster at the cost of producing sub-optimal solutions) for many of these  problems (see e.g., \cite{elkin-survey,dubhashi, khan-disc,khan-podc}).  Such algorithms can be useful for large-scale resource-constrained and dynamic networks where running time is crucial.
%\amitabh{I think below should either be here, or in related works;  compare to Lynch's - ours is  a 2-connectivity model - prove here. }
%\paragraph{Should we mention that Lynch et al's algorithm (STOC) can solve our problem in $O(n^2)$?} If we do, we can say that our algorithm is much faster. We can even maintain the density all the time. (If they want to do the same, they need to make more assumption so that the graph doesn't change so rapidly. They could end up with our general model.)
%insert \looseness -1
Our work differs from the above mentioned ones in that we address the issues in a dynamic setting, i.e., where edges of the network change over time.
Dynamic network topology and fault tolerance have always been core concerns of distributed computing~\cite{Attiya-WelchBook,lynch}. There are many models and a large volume of work in this area.
A notable recent model is the dynamic graph model introduced by Kuhn, Lynch and Oshman in \cite{KuhnLO10}. They introduced a  stability property called $T$-interval connectivity (for $T\ge 1$) which stipulates the existence of a stable connected spanning subgraph for every $T$ rounds. Though our models are not fully comparable (we allow our networks to get temporarily disconnected as long as messages eventually make their way through it),
%\amitabh{confirm this}),
% if the network stays connected at all times)
the graphs generated by our model are similar to theirs except for our limited rate of churn.
% (rather, a subset of) for $T \ge 2$.
% This is easy to see: since only a single edge is added or removed in a step, a spanning tree persists for at least two rounds if the graph stays connected.
They show that they can determine the size of the  network in $O(n^2)$ rounds
%\amitabh{Is this comparable? their counting is exact? Maybe, we should not mention this.}
and also give a method for approximate counting.
 We differ in that our bounds are sublinear in $n$ (when $D$ is small) and we  maintain our dense graphs at all times.

We work under the well-studied CONGEST model (see, e.g., \cite{peleg} and the references therein). Because of its realistic communication restrictions, there has been much research done in this model (e.g., see \cite{lynch,peleg,PK09}).  In particular, there has been much work done in designing very fast distributed approximation
algorithms (that are even faster at the cost of producing sub-optimal solutions) for many fundamental problems (see, e.g., \cite{elkin-survey,dubhashi,khan-disc,khan-podc}).
%Such algorithms can be useful for large-scale resource-constrained and dynamic networks where running time is crucial.
Among many graph problems studied, the densest subgraph problem falls into the ``global problem'' category where it seems that one needs at least $\Omega(D)$ rounds to compute or approximate (since one needs to at least know the number of nodes in the graph in order to compute the density). While most results we are aware of in this category were shown to have a lower bound of $\Omega(\sqrt{n/\log n})$, even on graphs with small diameter (see \cite{DasSarmaHKKNPPW11} and references therein), the densest subgraph problem is one example for which this lower bound does not hold.
%This gives the densest subgraph problem a different status from most global graph problems.

Our algorithm requires certain size estimation algorithms as a subroutine. An important tool that also addresses network size estimation is a \emph{Controller}.
%
%Controllers work by having a set of permits which can be requested and the request granted or rejected by designated nodes. They were introduced in~\cite{AfekAPSController-FOCS87} and have been implemented in the \emph{controlled dynamic model} which is a `polite' node dynamic model with nodes entering and leaving subject to permits from the resource controller.
%
Controllers were introduced in~\cite{AfekAPSController-FOCS87}  and they were implemented on `growing' trees, but this was later extended to a more general dynamic model~\cite{KormanKuttenControllerPODC07,EmekKormanController-DISC09}. Network size estimation itself is a fundamental problem in the distributed setting and closely related to other problems like leader election.  For anonymous networks and under some reasonable assumptions, exact size estimation  was shown to be impossible~\cite{CidonS-IPL95} as was leader election~\cite{AngluinSTOC80} (using symmetry concerns). Since then, many probabilistic estimation techniques have been proposed using exponential and geometric distributions~\cite{KuhnLO10,AggarwalKuttenFST93,MatiasA-WDAG89}. Of course, the problem is even more challenging in the dynamic setting.
%

%Our algorithms may be useful for developing self-* systems so self-* properties~\cite{Berns09DissectingSelf-*} and the dynamic models they use are worth mentioning here. Self-stabilization~\cite{Djikstra74SelfStabilizing,  DolevBookSelfStabilization} requires that the system converge to a valid configuration starting from any arbitrary state and this concept has been used for many
%
%. Eventual stabilization often guarantees safety throughout execution but progress only after stabilization, and has been used for many
%
%solutions~\cite{Dolev09EmpireofColoniesSelf-stabilizing,  KormanKMPODC11, BeauquierBK-JThCS11}. Some reconfigurable overlay network based models are node-dynamic in that nodes join and leave continously~\cite{Kuhn2005-Repairing,Amitabh-2010-PhdThesis}.
%
%A special class of this is the self-healing model where the algorithm can add a limited number of edges in response to a deletion; this has been shown to be useful for maintaining many invariants~\cite{Poor-SelfHealQueue2003, Ghosh07Self healingSystemsSurvey, PanduranganPODC11, HayesPODC09, HayesPODC08, SaiaTrehanIPDPS08}. In fact, in~\cite{SarmaTrehanEdgeNetSciComm2012}, the authors propose an algorithm to self-heal network density.
%
Self-* systems~\cite{Berns09DissectingSelf-*,Djikstra74SelfStabilizing,DolevBookSelfStabilization,KormanKMPODC11,Kuhn2005-Repairing,Poor-SelfHealQueue2003,Ghosh07Self-healingSystemsSurvey,PanduranganPODC11,HayesFG-DCJournal-springerlink,HayesPODC09,Amitabh-2010-PhdThesis} are worth mentioning here.
Often, a crucial condition for such systems is the initial detection of a particular state. In this respect, our algorithm can be viewed as a self-aware algorithm where the nodes monitor their state with respect to the environment, and this could be used for developing powerful self-* algorithms.
% for density maintenance.

%There has been much interest in self-* properties~\cite{Berns09DissectingSelf-*} such as self stabilization~\cite{Djikstra74SelfStabilizing,  DolevBookSelfStabilization, Dolev09EmpireofColoniesSelf-stabilizing, KormanKMPODC11, BeauquierBK-JThCS11} and self- healing~\cite{Poor-SelfHealQueue2003, Ghosh07Self healingSystemsSurvey, Amitabh-2010-PhdThesis, PanduranganPODC11, SarmaTrehanEdgeNetSciComm2012, HayesPODC09, HayesPODC08, SaiaTrehanIPDPS08}, not only in the theoretical community but also in the industry such as with IBM's autonomic computing initiative~\cite{IBMAutonomicManifesto, IBMAutonomicVision} and self-CHOP~\cite{IBMAutoComp-SelfChop}. In fact, in~\cite{SarmaTrehanEdgeNetSciComm2012}, the authors propose an algorithm to self-heal network density.  Often, a crucial condition for any self-* algorithmic is the initial detection of a particular state. In this aspect, our algorithm can be viewed as a self-aware algorithm where the nodes monitor their state with respect to the environment, and this could be used for developing powerful self-* algorithms for density maintainance.
%

%- references to network size estimation:
%
%
% %\amitabh{mention few other papers in the edge-dynamic setting e.g. Shay's etc}
%
%Our algorithms use techniques for network size estimation in a dynamic setting. Network size estimation itself is a fundamental problem in the distributed setting and closely related to other problems like leader election. For anonymous networks and under some reasonable assumptions, exact size estimation  was shown to be impossible~\cite{CidonS-IPL95} as was leader election~\cite{AngluinSTOC80} (using symmetry concerns). Since then, many probabilistic estimation techniques have been proposed using exponential and geometric distributions~\cite{KuhnLO10, AggarwalKuttenFST93, MatiasA-WDAG89}.
%%\amitabh{Expand this list if wanted}.
%Of course, the problem is even more challenging in the dynamic setting.


